Search Results

Documents authored by Karlin, Anna R.

Found 2 Possible Name Variants:

Karlin, Anna R.

Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.1
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)

Authors: Anna R. Karlin

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We describe recent joint work with Nathan Klein and Shayan Oveis Gharan showing that for any metric TSP instance, the max entropy algorithm studied by [Anna R. Karlin et al., 2021] returns a solution of expected cost at most 3/2-ε times the cost of the optimal solution to the subtour elimination LP and hence is a 3/2-ε approximation for the metric TSP problem. The research discussed comes from [Anna R. Karlin et al., 2021], [Anna R. Karlin et al., 2022] and [Anna R. Karlin et al., 2022].
Cite as

Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{karlin:LIPIcs.ICALP.2023.1,
  author =	{Karlin, Anna R.},
  title =	{{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1},
  URN =		{urn:nbn:de:0030-drops-180531},
  doi =		{10.4230/LIPIcs.ICALP.2023.1},
  annote =	{Keywords: Traveling Salesperson Problem, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.2
Matroid Partition Property and the Secretary Problem

Authors: Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A matroid M on a set E of elements has the α-partition property, for some α > 0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of M such that every independent set of 𝒫 is independent in M and for any weight function w:E → ℝ_{≥0}, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on M. We show that the complete binary matroid, B_d on 𝔽₂^d does not satisfy the α-partition property for any constant α > 0 (independent of d). Furthermore, we refute a recent conjecture of [Kristóf Bérczi et al., 2021] by showing the same matroid is 2^d/d-colorable but cannot be reduced to an α 2^d/d-colorable partition matroid for any α that is sublinear in d.
Cite as

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2,
  author =	{Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title =	{{Matroid Partition Property and the Secretary Problem}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-175051},
  doi =		{10.4230/LIPIcs.ITCS.2023.2},
  annote =	{Keywords: Online algorithms, Matroids, Matroid secretary problem}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITCS.2018
LIPIcs, Volume 94, ITCS'18, Complete Volume

Authors: Anna R. Karlin

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
LIPIcs, Volume 94, ITCS'18, Complete Volume
Cite as

9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{karlin:LIPIcs.ITCS.2018,
  title =	{{LIPIcs, Volume 94, ITCS'18, Complete Volume}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018},
  URN =		{urn:nbn:de:0030-drops-84419},
  doi =		{10.4230/LIPIcs.ITCS.2018},
  annote =	{Keywords: Theory of Computation, Mathematics of Computing}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITCS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Anna R. Karlin

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{karlin:LIPIcs.ITCS.2018.0,
  author =	{Karlin, Anna R.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.0},
  URN =		{urn:nbn:de:0030-drops-83104},
  doi =		{10.4230/LIPIcs.ITCS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.43
Carpooling in Social Networks

Authors: Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair. We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness. A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness ~Theta(sqrt(d)) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Omega(log^{1/3}(d)) to Omega(log(d)). We also show that the competitive ratio of global random greedy against adaptive adversaries is Omega(d).
Cite as

Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach. Carpooling in Social Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fiat_et_al:LIPIcs.ICALP.2016.43,
  author =	{Fiat, Amos and Karlin, Anna R. and Koutsoupias, Elias and Mathieu, Claire and Zach, Rotem},
  title =	{{Carpooling in Social Networks}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.43},
  URN =		{urn:nbn:de:0030-drops-63234},
  doi =		{10.4230/LIPIcs.ICALP.2016.43},
  annote =	{Keywords: Online algorithms, Fairness, Randomized algorithms, Competitive ratio, Carpool problem}
}

Karlin, Anna

Document
DOI: 10.4230/DagSemRep.243
Competitive Algorithms (Dagstuhl Seminar 99251)

Authors: Amos Fiat, Anna Karlin, and Gerhard Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Amos Fiat, Anna Karlin, and Gerhard Woeginger. Competitive Algorithms (Dagstuhl Seminar 99251). Dagstuhl Seminar Report 243, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{fiat_et_al:DagSemRep.243,
  author =	{Fiat, Amos and Karlin, Anna and Woeginger, Gerhard},
  title =	{{Competitive Algorithms (Dagstuhl Seminar 99251)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{243},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.243},
  URN =		{urn:nbn:de:0030-drops-151295},
  doi =		{10.4230/DagSemRep.243},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact